/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-12-19
 * Time: 22:59
 */


//快排+二分
public class Solution {
    //快速排序的一遍
    public int partition(int[] nums,int left,int right){
        int pivot=nums[left];
        int start=left;
        int end=right;
        while(start<end){
            while(start<end&&nums[end]>=pivot){
                end--;
            }
            while(start<end&&nums[start]<=pivot){
                start++;
            }
            //交换,小的放左边,大的放右边
            swap(nums,start,end);
        }
        //找到正确的位置了,交换最左边的元素和正确位置的元素
        nums[left]=nums[start];
        nums[start]=pivot;
        return start;
    }

    public void swap(int[] nums,int index1,int index2){
        int temp=nums[index1];
        nums[index1]=nums[index2];
        nums[index2]=temp;
    }

    public int find(int[] nums,int k,int left,int right){
        int length=nums.length;
        int index=partition(nums,left,right);
        if(index==length-k){
            System.out.println(index);
            //找到了第k大的元素
            return nums[length-k];
        }else if(index<length-k){
            //偏小
            return find(nums,k,index+1,right);
        }else{
            return find(nums,k,left,index-1);
        }
    }
    public int findKthLargest(int[] nums, int k) {
        int length=nums.length;
        //对于k超出数组范围做出处理
        if(k>length){
            if(k%length==0){
                k=length;
            }else{
                k=k%length;
            }
        }
        return find(nums,k,0,nums.length-1);
    }
}
